#ifndef _CAL_FOL_IMPL
#define _CAL_FOL_IMPL

#include "dfa_base_loc.h"
#include "dfa_base_str.h"
#include "Dfa_base.h"

// calculate the follow value
namespace cal_fol_loc {
	void cal_end_full(dfa_base_str::Fol_val &fols, dfa_base_str::Lex_oper &tree);
	void reset_pos(dfa_base_str::Lex_oper &tree, size_t &cur_pos);
}
dfa_base_str::Fol_val &dfa_base_loc::cal_fol(dfa_base_str::Reg_tree &tree, std::ostream &err) {
	using namespace dfa_base_str;
	size_t cur_pos=0;

	cal_fol_loc::reset_pos(*tree.tree, cur_pos);
	dfa_base_str::End_mark *end=0;
	Lex_oper *reg=0;
	Fol_val *fols=0;
	try {
		end = new dfa_base_str::End_mark(cur_pos++);	// add end mark
		reg = new dfa_base_str::Concate(*tree.tree, *end);
		tree.tree = reg;
		fols = new Fol_val(cur_pos);			// build a follow value vector
		cal_fol_loc::cal_end_full(*fols, *reg);
		return *fols;
	} catch(...) {
		if( fols )		// 'end' and 'reg' can't be deleted, since it has been a part of tree.tree
			delete fols;
		throw dfa_base::Dfa_base::Out_of_mem();
	}
}
void cal_fol_loc::cal_end_full(dfa_base_str::Fol_val &fols, dfa_base_str::Lex_oper &tree){	
	using namespace dfa_base_str;
	Lex_oper *reg_tree = &tree;
	if(Start *start = dynamic_cast<Start *> (reg_tree) ) {
		cal_end_full(fols, start->child());
	} else if( Kleen *kleen = dynamic_cast<Kleen *>(reg_tree) ) {
		cal_end_full(fols, kleen->child());
		const dfa_base_str::Pos_set &last = kleen->last();			// fol[last()] U= first();
		const dfa_base_str::Pos_set &first = kleen->first();
		for(mylib::Set<int>::const_iterator P=last.begin(); P!=last.end(); P++)
			fols[*P].pos_set += first;
	} else if( One_more *one_more = dynamic_cast<One_more *>(reg_tree) ) {
		cal_end_full(fols, one_more->child());
		const dfa_base_str::Pos_set &last = one_more->last();			// fol[last()] U= first();
		const dfa_base_str::Pos_set &first = one_more->first();
		for(mylib::Set<int>::const_iterator P=last.begin(); P!=last.end(); P++)
			fols[*P].pos_set += first;
	} else if( Zero_one *zero_one = dynamic_cast<Zero_one *>(reg_tree)) {
		cal_end_full(fols, zero_one->child());
	} else if(Concate *concate = dynamic_cast<Concate *>(reg_tree)) {
		cal_end_full(fols, concate->l_child());
		cal_end_full(fols, concate->r_child());
		const dfa_base_str::Pos_set &last = concate->l_child().last();			// fol[last()] U= first();
		const dfa_base_str::Pos_set &first = concate->r_child().first();
		for(mylib::Set<int>::const_iterator P=last.begin(); P!=last.end(); P++)
			fols[*P].pos_set += first;
	} else if(Union *un = dynamic_cast<Union *>(reg_tree)) {
		cal_end_full(fols, un->l_child());
		cal_end_full(fols, un->r_child());
	} else if( Suffix *suffix = dynamic_cast<Suffix *>(reg_tree)) {
		cal_end_full(fols, suffix->l_child());
		cal_end_full(fols, suffix->r_child());
		const dfa_base_str::Pos_set &last = suffix->l_child().last();			// fol[last()] U= first();
		const dfa_base_str::Pos_set &first = suffix->r_child().first();
		for(mylib::Set<int>::const_iterator P=last.begin(); P!=last.end(); P++)
			fols[*P].pos_set += first;
	} else if( Reg_base *base = dynamic_cast<Reg_base *>(reg_tree) ) {
		fols[base->position()].oper = base;
	} else if( dfa_base_str::End_mark *end = dynamic_cast<End_mark *> (reg_tree) ) {
		fols[end->position()].oper = end;
	} else
		;
}
void cal_fol_loc::reset_pos(dfa_base_str::Lex_oper &tree, size_t &cur_pos) {
	using namespace dfa_base_str;
	Lex_oper *reg_tree = &tree;
	if( Reg_base *base = dynamic_cast<Reg_base *>(reg_tree) ) {
		base->set_pos(cur_pos++);
	} else if( dynamic_cast<End_mark *> (reg_tree) ) {
		;
	} else if(Start *start = dynamic_cast<Start *> (reg_tree) ) {
		reset_pos(start->child(), cur_pos);
	} else if( dynamic_cast<Start_line *> (reg_tree) ) {
		;
	} else if( Kleen *kleen = dynamic_cast<Kleen *>(reg_tree) ) {
		reset_pos(kleen->child(), cur_pos);
	} else if( One_more *one_more = dynamic_cast<One_more *>(reg_tree) ) {
		reset_pos(one_more->child(), cur_pos);
	} else if( Zero_one *zero_one = dynamic_cast<Zero_one *>(reg_tree)) {
		reset_pos(zero_one->child(), cur_pos);
	} else if(Concate *concate = dynamic_cast<Concate *>(reg_tree)) {
		reset_pos(concate->l_child(),cur_pos);
		reset_pos(concate->r_child(),cur_pos);
	} else if(Union *un = dynamic_cast<Union *>(reg_tree)) {
		reset_pos(un->l_child(), cur_pos);
		reset_pos(un->r_child(), cur_pos);
	} else if( Suffix *suffix = dynamic_cast<Suffix *>(reg_tree)) {
		reset_pos(suffix->l_child(), cur_pos);
		reset_pos(suffix->r_child(), cur_pos);
	} else if (Eplilon *eplilon = dynamic_cast<Eplilon *>(reg_tree))
		;
	else {
		throw dfa_base::Dfa_base::Err_input();
	}
}
#endif
